class Solution {
public:
    vector<long long> findXSum(vector<int>& nums, int k, int x) {
        vector<long long> res(nums.size() - k + 1);
        set<pair<int, int>> fi, se;
        unordered_map<int, int> cnt;
        long long sum = 0;

        auto add = [&](int x) {
            pair<int, int> a = { cnt[x], x };
            if (a.first == 0) return;

            if (!fi.empty() && a > *fi.begin()) {
                sum += (long long)a.first * a.second;
                fi.insert(a);
            }
            else se.insert(a);
            };

        auto del = [&](int x) {
            pair<int, int> a = { cnt[x], x };
            if (a.first == 0) return;

            auto it = fi.find(a);
            if (it != fi.end()) {
                sum -= (long long)a.first * a.second;
                fi.erase(it);
            }
            else se.erase(a);
            };

        auto fi2se = [&]() {
            pair<int, int> a = *fi.begin();
            sum -= (long long)a.first * a.second;
            se.insert(a);
            fi.erase(a);
            };

        auto se2fi = [&]() {
            pair<int, int> a = *se.rbegin();
            sum += (long long)a.first * a.second;
            fi.insert(a);
            se.erase(a);
            };

        for (int i = 0; i < nums.size(); i++) {
            del(nums[i]);
            cnt[nums[i]]++;
            add(nums[i]);

            int j = i - k + 1;
            if (j < 0) continue;

            while (!se.empty() && fi.size() < x) se2fi();
            while (fi.size() > x) fi2se();

            res[j] = sum;
            del(nums[j]);
            cnt[nums[j]]--;
            add(nums[j]);
        }

        return res;
    }
};